/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    const res = []
    let path = []
    const dfs = function (num, capacity) {
        // 容量小于0直接返回
        if (capacity < 0) return
        // 还没到k就凑满了 不符合要求直接返回
        if(capacity === 0 && path.length !== k) return
        // 容量为0并且长度满足要求，符合条件
        if (capacity === 0 && path.length === k) {
            res.push(path.slice())
            return
        }
        for(let j = num; j <= 9; j++) {
            path.push(j)
            dfs(j + 1, capacity - j)
            path.pop()
        }
    }
    for(let i = 1; i <= n; i++) {
        // 剪枝，必须以i开头。并且后面只能去当前数字后面的数
        path.push(i)
        dfs(i + 1, n - i)
        path.pop()
    }
    return res
};
// console.log(combinationSum3(3, 9));
console.log(combinationSum3(2, 18));
console.log(combinationSum3(9, 45));